

//
//  BinaryTree_remove.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/16.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension BinaryTree {
    
    /// 删除二叉树中位于node位置的节点及其后代
    /// 返回被删除的总量
    public func remove(_ node: Node<Element>) -> Int {
        
        let removedCount = node.count
        if node === _root {
            _root = nil
        } else if node.parent?.lchild === node {
            node.parent?.lchild = nil
        } else if node.parent?.rchild === node {
            node.parent?.rchild = nil
        }
        _size -= removedCount
        updateHeightAbove(node.parent)
        return removedCount
    }
}
